package com.mashibing.class13;

/**
 * 给定一棵二叉树的头节点head，和另外两个节点a和b。
 *         返回a和b的最低公共祖先
 * 判断规则有4中情况
 * 1) 汇聚点与x无关 (x不是最低汇聚点)
 *  1.1) 左有答案
 *  1.2) 右有答案
 *  1.3) a,b不全
 * 2) 汇聚点与x有关 (x是答案)
 *  2.1)左有答案 右也有答案 在x这里最初汇聚
 *  2.2)x本身就是a节点, 左树或右树发现了b
 *  2.3)x本身就是b节点, 左树或右树发现了a
 */
public class Code03_lowestAncestor {
    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }
    public static Node lowestAncestor1(Node head, Node a, Node b) {
        return process(head, a, b).ans;
    }

    public static class Info{
        public boolean findA;
        public boolean findB;
        public Node ans;

        public Info(boolean findA, boolean findB, Node ans) {
            this.findA = findA;
            this.findB = findB;
            this.ans = ans;
        }
    }

    public static Info process(Node node, Node a, Node b){
        if (node==null){
            return new Info(false,false,null);
        }
        Info leftInfo = process(node.left, a, b);
        Info rightInfo = process(node.right, a, b);

        boolean findA = (node==a) || leftInfo.findA || rightInfo.findA;
        boolean findB = (node==b) || leftInfo.findB || rightInfo.findB;;
        Node ans = null;
        if (leftInfo.ans != null){
            ans = leftInfo.ans;
        }else if(rightInfo.ans != null){
            ans = rightInfo.ans;
        }else{
            if (findA&&findB){
                ans = node;
            }
        }
        return new Info(findA,findB,ans);
    }
}
